"""
LCP 40. 心算挑战
简单
相关标签
相关企业
「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

示例 1：

输入：cards = [1,2,8,9], cnt = 3

输出：18

解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

示例 2：

输入：cards = [3,3,1], cnt = 1

输出：0

解释：不存在获取有效得分的卡牌方案。

提示：

1 <= cnt <= cards.length <= 10^5
1 <= cards[i] <= 1000
"""
from typing import List


class Solution:
    """
    思路：先把数组按照降序排列。然后取前cnt个数，此时有两种情况：
    1.前cnt个数的和为偶数，那么符合题意，直接返回其和
    2.前cnt个数的和为奇数，那么此时有两个方案：
    (1)用后面最大的奇数代替前cnt中最小的偶数
    (2)用后面最大的偶数代替前cnt中最小的奇数
    这两个方案都可以得出一个偶数，比较它们谁更大，更大的结果即为所求
    """
    def maximumScore(self, cards: List[int], cnt: int) -> int:
        """
        cards.sort(reverse=True)
        maxnum = temp = ji = ou = fji = fou = 0
        for i in range(cnt):
            # 找出最小的奇数和偶数，因为是降序排列，所以最后进入循环的一定是偏小的奇数或者偶数
            if cards[i]%2 == 0:
                ou = cards[i]
            else:
                ji = cards[i]
            temp+=cards[i]
        if temp%2==0:
            return temp
        # temp为奇数
        else:
            for i in range(cnt,len(cards)):
                # 如果下一张为偶数
                if cards[i] %2 == 0:
                    # 只用对比第一个奇数或者第一个偶数即可，因为数列是降序排列的，第二个第三个肯定比第一个小，故求最大值不用不用比较
                    if ji !=0 and fji==0:
                        # 用后面最大的偶数代替前cnt中最小的奇数
                        maxnum = max(maxnum,temp- ji + cards[i])
                        fji = 1
                # 如果下一张为奇数
                else:
                    if ou != 0 and fou==0 :
                        # 用后面最大的奇数代替前cnt中最小的偶数
                        maxnum = max(maxnum, temp - ou + cards[i])
                        fou = 1
        return maxnum
        """
        # 1 <= cards[i] <= 1000
        val=[0]*1001
        # 此时val数组里的索引就对应着cards的值，而数组val[i]里面的值则代表在cards里面，i这样的值有count=val[i]个
        for card in cards:
            val[card]+=1
        # print(val)
        maxnum = temp = ji = ou = selected = 0
        # 数字的范围是从 1 到 1000，而索引就代表值，所以是range(1000,0,-1)
        for i in range(1000,0,-1):

            while val[i]>0 and selected < cnt:
                if i%2==0:
                    # 倒着遍历的，所以最后加入循环的一定最小
                    ou = i
                else:
                    ji = i
                selected+=1
                val[i]-=1
                temp+=i
        # print(ji,ou,temp,val)
        if temp % 2 == 0:
            return temp
# 此时，非常重要的一点是，在我们挑出前cnt个数后，val[i]是-1了的。那么此时val里面也就不包含我们已经选择过cnt那几张，此时就可以直接用val表。
        else:
            for i in range(1000, 0, -1):
                # while val[i] > 0:！！！注意此处wile和if的区别
                if val[i] > 0:
                    if i%2==0 and ji!=0:
                        maxnum = max(maxnum,temp-ji+i)
                    elif i%2==1 and ou!=0:
                        maxnum = max(maxnum, temp - ou + i)

        return maxnum




# #         先把奇数偶数分组排序，再使用贪心算法每次拿最大的。限制条件：1.偶数可以任意个 2.奇数只能拿偶数个，因为要保证最后的数是偶数
#         ji = sorted([j for j in cards if j%2==1],reverse=True)
#         ou = sorted([o for o in cards if o%2==0],reverse=True)
#         print(ou,ji)
#         max_num=0
#         # 从偶数组里面选择i个数据
#         for i in range(cnt+1):
#             if (cnt-i)%2==1:
#                 continue
#             if i> len(ou) or (cnt-i)> len(ji):
#                 continue
#             cur = sum(ou[:i])+sum(ji[:cnt-i])
#             max_num = max(max_num,cur)
#         return max_num
#         evens = sorted([x for x in cards if x % 2 == 0], reverse=True)
#         odds = sorted([x for x in cards if x % 2 == 1], reverse=True)
#
#         # 如果卡牌总数不足，直接返回 0
#         if len(evens) + len(odds) < cnt:
#             return 0
#
#         # 初始化最大得分
#         max_score = 0
#
#         # 枚举从 evens 中选 i 张卡牌
#         for i in range(max(0, cnt - len(odds)), min(cnt, len(evens)) + 1):
#             # 奇数卡牌的数量必须是偶数，且总共选 cnt 张卡牌
#             if (cnt - i) % 2 == 0:
#                 # 当前组合的得分
#                 current_score = sum(evens[:i]) + sum(odds[:cnt - i])
#                 max_score = max(max_score, current_score)
#
#         return max_score



if __name__ == '__main__':
    print(Solution().maximumScore(cards=[10,11,9,6,5,4],cnt=1))
